/**
 * https://leetcode-cn.com/problems/unique-binary-search-trees/
 * 不同的二叉搜索树
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 * @param n 
 */
const numTrees = (n: number): number => {
    const Gn: number[] = new Array(n + 1).fill(0)
    
    // 初始值
    Gn[0] = 1;
    Gn[1] = 1;

    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            Gn[i] += (Gn[j - 1] * Gn[i - j])
        }
    }

    return Gn[n]
};

console.log(numTrees(3))